20 Exos Complexité Correction
Exercice 1 - Classes de complexité⚓︎
Voici quelques complexités d’algorithme, cherchons les complexités de référence qui sont du même ordre de grandeur.
- \(n^3+5n^2+2=\mathcal{O}(n^3)\) – complexité cubique
- \(\frac13n^4+7n^3+2n=\mathcal{O}(n^4)\) – complexité polynomiale
- \(2+3n\log(n)= \mathcal{O}(\log(n))\) – complexité logarithmique
- \(n\log(n)+2^n+7n^3=\mathcal{O}(n^3)\) – complexité cubique
- \(n!+8^n+9n^2=\mathcal{O}(n!)\) – complexité factorielle
Exercice 2 - Fonction mystère⚓︎
Un élève un peu anxieux a réalisé le code suivant.
def mystere(L):
nombre = L[0]
n = len(L)
for i in range(n):
if nombre < L[i]:
nombre = L[i]
# Deuxième verif au cas où
for j in range(i):
if nombre < L[j]:
nombre = L[j]
return nombre
print(mystere([1,2,-8,14,17,10,0]))
-
Que fait cette fonction ?
Cette fonction retourne le minimum de la liste L passée en paramètre. -
Quel est le temps d’exécution au pire des cas ? Quelle est la classe de complexité de cet algorithme ?
| instruction | nb de calculs | Total |
|---|---|---|
| nombre = L[0] | 1 calcul | 1 |
| n = len(L) | 1 calcul | 1 |
| for i in range(n): | n boucles de ce qui suit | |
| if nombre < L[i]: | 1 test | n en tout |
| nombre = L[i] | 1 calcul si pire des cas | n en tout |
| for j in range(i): | i boucles | |
| if nombre < L[j]: | 1 test | 1+2+3+...+n \(=\dfrac{n(n+1)}{2}\) |
| nombre = L[j] | n'arrive jamais | 0 |
Total de \(\dfrac{n^2 + n}{2} + 2n + 2 = \mathcal{O}(n^2)\)
Cette fonction est dans la classe de complexité quadratique.
Exercice 3 - Parcours séquentiel d’une liste⚓︎
On écrit une fonction est_element qui prend en paramètres un objet a et une liste L et retourne un booléen traduisant la véracité de l’affirmation « l’objet a est un élément de la liste L ».
def est_element(a, L):
for elt in L:
if elt == a:
return True
return False
Quelle est la classe de complexité de cet algorithme ?
On a une boucle de la longueur de la liste (au pire), avec à chaque fois un test. Cette fonction est dans la classe de complexité linéaire \(\mathcal{O}(n)\).
Exercice 4 - Calcul de moyenne⚓︎
On écrit un programme en Python calculant la moyenne d’une liste de flottants.
def moyenne(liste):
if not(liste):
return None
somme = 0
for val in liste:
somme += val
return somme / len(liste)
Quelle est la classe de complexité de cet algorithme ?
On a une boucle de la longueur de la liste, avec à chaque fois un calcul et une affectation. Cette fonction est dans la classe de complexité linéaire \(\mathcal{O}(n)\).
Exercice 5 - Recherche d’un extremum⚓︎
On écrit un programme en Python recherchant le plus grand élément d’une liste de flottants.
def recherche_max(liste):
if not(liste):
return None
val = liste[0]
for elt in liste:
if elt > val:
val = elt
return val
Quelle est la classe de complexité de cet algorithme ?
On a une boucle de la longueur de la liste, avec à chaque fois un test. Cette fonction est dans la classe de complexité linéaire \(\mathcal{O}(n)\).
Exercice 6 - Recherche par dichotomie⚓︎
On écrit en Python le programme de recherche par dichotomie.
def recherche_dichotomique(liste, element):
"""
liste doit être triée dans l'ordre croissant
Renvoie True si l'élément est dans la liste, False sinon
"""
indice_debut = 0
indice_fin = lent(liste) - 1
while indice_debut <= indice_fin:
indice_centre = (indice_debut + indice_fin) // 2
valeur_centrale = liste(indice_centre)
if valeur_centrale == element: # element est trouvé !
return indice_centrale
elif valeur_centrale < element:# on cherche dans la seconde moitié
indice_debut = indice_centre + 1
else:# on cherche dans la première moitié
indice_fin = indice_centre - 1
return -1
Quel est le temps d’exécution au pire des cas ? Quelle est la classe de complexité de cet algorithme ?
A chaque tour de boucle while, la longueur de l'intervalle est divisée par \(2\). On a donc \(\log(n)\) tours de boucle.
La classe de complexité est logarithmique \(\mathcal{O}(\log(n))\).